home *** CD-ROM | disk | FTP | other *** search
/ CU Amiga Super CD-ROM 19 / CU Amiga Magazine's Super CD-ROM 19 (1998)(EMAP Images)(GB)[!][issue 1998-02].iso / CUCD / Programming / LEDA / source / src / dict / _bin_tree.c < prev    next >
Encoding:
C/C++ Source or Header  |  1994-11-16  |  14.9 KB  |  636 lines
  1. /*******************************************************************************
  2. +
  3. +  LEDA  3.1c
  4. +
  5. +
  6. +  _bin_tree.c
  7. +
  8. +
  9. +  Copyright (c) 1994  by  Max-Planck-Institut fuer Informatik
  10. +  Im Stadtwald, 6600 Saarbruecken, FRG     
  11. +  All rights reserved.
  12. + 
  13. *******************************************************************************/
  14.  
  15.  
  16.  
  17. //------------------------------------------------------------------------------
  18. //
  19. //  bin_tree: base class for all binary tree  types
  20. //
  21. //  leaf oriented & doubly linked 
  22. //
  23. //------------------------------------------------------------------------------
  24.  
  25. #include <LEDA/impl/bin_tree.h>
  26.  
  27.  
  28. bin_tree_node* bin_tree::lookup(GenPtr x) const
  29. { bin_tree_node* p = locate(x);
  30.   if (p && cmp(p->k,x) == 0) return p;
  31.   return 0;
  32. }
  33.  
  34. void  bin_tree::change_inf(bin_tree_node* p,GenPtr y) 
  35. { clear_inf(p->i);
  36.   copy_inf(y);
  37.   p->i = y; 
  38.  }
  39.  
  40.  
  41. //------------------------------------------------------------------------------
  42. // locate(x) : returns pointer to leave with successor or predessor key of x
  43. //------------------------------------------------------------------------------
  44.  
  45. bin_tree_node* bin_tree::locate(GenPtr x) const
  46. { 
  47.   if (count==0) return 0;
  48.   return  int_type() ? int_search(x) : search(x);
  49. }
  50.  
  51.  
  52. //------------------------------------------------------------------------------
  53. // locate_succ(x) : returns pointer to leave with minimal key >= x
  54. //             nil if tree empty
  55. //------------------------------------------------------------------------------
  56.  
  57. bin_tree_node* bin_tree::locate_succ(GenPtr x) const
  58. { if (count==0) return 0;
  59.   bin_tree_node* p =  int_type() ? int_search(x) : search(x);
  60.   return (cmp(x,p->k) > 0) ? succ(p) : p ;
  61.  }
  62.  
  63.  
  64.  
  65. //------------------------------------------------------------------------------
  66. // locate_pred(x) : returns pointer to leave with maximal key <= x
  67. //                  nil if tree empty
  68. //------------------------------------------------------------------------------
  69.  
  70. bin_tree_node* bin_tree::locate_pred(GenPtr x) const 
  71. { if (count==0) return 0;
  72.   bin_tree_node* p =  int_type() ? int_search(x) : search(x);
  73.   return (cmp(x,p->k) < 0) ? pred(p) : p ;
  74.  }
  75.  
  76.  
  77.  
  78. //------------------------------------------------------------------------------
  79. // search(x) : returns pointer to leave with minimal key >= x
  80. //------------------------------------------------------------------------------
  81.  
  82. bin_tree_node* bin_tree::search(GenPtr x) const
  83. {
  84.   bin_tree_node* p = root();
  85.  
  86.   while (p->is_node())
  87.        p = (cmp(x,p->k) <= 0) ? p->child[left] : p->child[right];
  88.  
  89.   return p;
  90.  }
  91.  
  92.  
  93.  
  94. //------------------------------------------------------------------------------
  95. // int_search : search for integer key 
  96. //------------------------------------------------------------------------------
  97.  
  98. bin_tree_node* bin_tree::int_search(GenPtr x) const
  99. {
  100.   bin_tree_node* p = root();
  101.  
  102.   while (p->is_node())
  103.        p = (long(x) <= long(p->k)) ? p->child[left] : p->child[right];
  104.  
  105.   return p;
  106.  }
  107.  
  108.  
  109.  
  110. //------------------------------------------------------------------------------
  111. // insert(x,y,ii):
  112. // inserts new leaf with key x and info y, sets info of new inner node to ii
  113. // returns pointer to the new leaf
  114. //------------------------------------------------------------------------------
  115.  
  116. bin_tree_node* bin_tree::insert( GenPtr x, GenPtr y, GenPtr ii)
  117. {  
  118.   // key x, inf y, iinf ii
  119.  
  120.   bin_tree_node* p;
  121.  
  122.    if (count==0)  // tree is empty 
  123.      { copy_key(x);
  124.        copy_inf(y);
  125.        p = new bin_tree_node(x,y,leaf_balance());
  126.        p->corr = &ROOT;
  127.        ROOT.i = ii;
  128.        min_ptr() = p;
  129.        root() = p;
  130.        p->parent = &ROOT;
  131.        p->child[right] = p;
  132.        p->child[left] = p;
  133.        count = 1;
  134.      }
  135.    else
  136.      { p = (int_type()) ? int_search(x) : search(x);
  137.        p = insert_at_item(p,x,y,ii);
  138.       }
  139.  
  140.    return p ;
  141.  }
  142.  
  143.  
  144.  
  145. bin_tree_node* bin_tree::insert_at_item(bin_tree_node* p, GenPtr x, GenPtr y, 
  146.                                                                     GenPtr ii)
  147. {
  148.  
  149.    bool insert_left;  //  true <==> insert new leaf q to the left of p
  150.  
  151.    copy_inf(y);
  152.                    
  153.    if ( int_type() )
  154.      { if ( long(x) == long(p->k) ) // x already stored in tree, overwrite info
  155.        { clear_inf(p->i);
  156.          p->i = y;
  157.          return p;
  158.         }
  159.        insert_left = (long(x) < long(p->k));
  160.       }
  161.    else
  162.       { int c = cmp(x,p->k);
  163.         if ( c == 0 )
  164.         { clear_inf(p->i);
  165.           p->i = y;
  166.           return p;
  167.          }
  168.         insert_left = (c < 0);
  169.         copy_key(x);
  170.        }
  171.  
  172.    int b = (count==1) ? root_balance() : node_balance();
  173.  
  174.    count++;
  175.  
  176.    bin_tree_node* q = new bin_tree_node(x,y,leaf_balance()); // new leaf
  177.    bin_tree_node* r = new bin_tree_node(0,0,b);              // new inner node
  178.    bin_tree_node* u = p->parent; 
  179.  
  180.    q->parent = r;
  181.    p->parent = r;
  182.    r->parent = u;
  183.    r->corr = nil;
  184.  
  185.  
  186.    if (p == u->child[left])
  187.       u->child[left] = r;
  188.    else
  189.       u->child[right] = r;
  190.  
  191.    // insertion of q, adjusting key & inf of corresponding inner nodes,
  192.    // double-chaining with neighbors, checking min pointer, ...
  193.  
  194.    if (insert_left) // insert q left of p
  195.       { r->k = x;
  196.         q->corr = r;
  197.         r->i = ii;
  198.         r->child[left] = q;
  199.         r->child[right]= p;
  200.         u = p->child[left];
  201.         q->child[left]  = u;
  202.         q->child[right] = p;
  203.         u->child[right] = q;
  204.         p->child[left]  = q;
  205.         if ( p == min_ptr() ) min_ptr() = q;     
  206.        }
  207.     else         // insert q right of p
  208.       { bin_tree_node* pc = p->corr; 
  209.         r->k = p->k;
  210.         r->i = pc->i;
  211.         pc->i = ii;
  212.         q->corr = pc;
  213.         p->corr = r;
  214.         r->child[left] = p;
  215.         r->child[right]= q;
  216.         u = p->child[right];
  217.         q->child[left]  = p;
  218.         q->child[right] = u;
  219.         u->child[left] = q;
  220.         p->child[right] = q;
  221.        }
  222.  
  223.     propagate_modification(1,r,p);
  224.     propagate_modification(2,r,q);
  225.  
  226.     if (r != root()) insert_rebal(r);
  227.  
  228.     return q;
  229.  
  230. }
  231.  
  232.  
  233.  
  234. //------------------------------------------------------------------------------
  235. // del(x) 
  236. // removes leaf with key x from the tree
  237. // overwrites possible copy of x in an inner node (if key type is not integer)
  238. //------------------------------------------------------------------------------
  239.  
  240. void bin_tree::del(GenPtr x)
  241. {
  242.   bin_tree_item v;
  243.  
  244.   if (count == 0) return;  // tree is empty
  245.  
  246.   if ( int_type() )
  247.     { v = int_search(x);
  248.       if (long(v->k) == long(x)) del_item(v);
  249.      }
  250.   else
  251.     { v = search(x);
  252.       if ( cmp(v->k,x) == 0 ) del_item(v);
  253.      }
  254.  
  255.  
  256.  }
  257.  
  258.  
  259. void bin_tree::del_item(bin_tree_item v)
  260. {
  261.   bin_tree_item w;
  262.   bin_tree_item p = v->parent;
  263.   bin_tree_item u = v->corr;
  264.  
  265.   clear_key(v->k);
  266.   clear_inf(v->i);
  267.  
  268.   // overwrite copy of key in corresponding inner node u by its predecessor,
  269.   // but keep its information (not necessary in the case that v is a left child)
  270.  
  271.   if (v != p->child[left]) 
  272.   { bin_tree_node* pred =  v->child[left];
  273.     u->k = pred->k;
  274.     clear_iinf(pred->corr->i);
  275.     pred->corr = u;
  276.   }
  277.   else
  278.     clear_iinf(u->i);
  279.  
  280.   count--;
  281.  
  282.   if (count == 0)      // tree is now empty
  283.   { root() = min_ptr() = nil;
  284.     delete v;
  285.     return;
  286.    } 
  287.  
  288.  
  289.   bin_tree_node* pred = v->child[left];
  290.   bin_tree_node* succ = v->child[right];
  291.  
  292.   // link neighbors
  293.   pred->child[right] = succ; 
  294.   succ->child[left] = pred;
  295.  
  296.   // adjust min pointer
  297.   if ( v == min_ptr() ) min_ptr() = succ;
  298.  
  299.  
  300.   // replace p by sibling w of v
  301.  
  302.   u = p->parent;
  303.   w = p->child[left];
  304.   if (v == w) w =  p->child[right];
  305.   w->parent = u;
  306.   if (p == u->child[left])
  307.      u->child[left] = w;
  308.   else
  309.      u->child[right] = w;
  310.  
  311.                                 //     u             u            u
  312.                                 //     |             |            |
  313.                                 //     p     or      p    --->    w
  314.                                 //    / \           / \
  315.                                 //   v   w         w   v
  316.  
  317.   propagate_modification(3,u,w);
  318.  
  319.   // rebalance tree, if necessary
  320.  
  321.   if (w != root()) del_rebal(w,p);
  322.  
  323.   delete v;
  324.   delete p;
  325.  
  326. }
  327.  
  328.  
  329. //------------------------------------------------------------------
  330. // concatenate
  331. //------------------------------------------------------------------
  332.  
  333. bin_tree& bin_tree::conc(bin_tree&) 
  334. { error_handler(1,"sorry, bin_tree::conc not implemented"); 
  335.   return *this;
  336.  }
  337.  
  338. //------------------------------------------------------------------
  339. // split at item
  340. //------------------------------------------------------------------
  341.  
  342. void bin_tree::split_at_item(bin_tree_node*,bin_tree&,bin_tree&) 
  343. { error_handler(1,"sorry, bin_tree::split_at_item not implemented"); }
  344.  
  345.  
  346. //------------------------------------------------------------------
  347. // reverse items
  348. //------------------------------------------------------------------
  349.  
  350. void bin_tree::reverse_items(bin_tree_node* v, bin_tree_node* w)
  351. {
  352.   bin_tree_node* l = v;
  353.   bin_tree_node* r = w;
  354.  
  355.   while (l != r && r->child[right] != l) 
  356.   {
  357.     bin_tree_node* pl = l->parent;
  358.     bin_tree_node* pr = r->parent;
  359.     bin_tree_node* cl = l->corr;
  360.     bin_tree_node* cr = r->corr;
  361.  
  362.  
  363.     // exchange l and r
  364.  
  365.    if (pl == pr)
  366.      { pl->child[left] = r;
  367.        pl->child[right] = l;
  368.       }
  369.    else
  370.      { if (l == pl->child[left])
  371.           pl->child[left] = r;
  372.        else
  373.           pl->child[right] = r;
  374.     
  375.        r->parent = pl;
  376.     
  377.        if (r == pr->child[left])
  378.           pr->child[left] = l;
  379.        else
  380.           pr->child[right] = l;
  381.     
  382.        l->parent = pr;
  383.       }
  384.   
  385.  
  386.    // update corresponding inner nodes
  387.  
  388.    l->corr = cr;
  389.    cr->k = l->k;
  390.  
  391.    r->corr = cl;
  392.    cl->k = r->k;
  393.  
  394.    l = l->child[right]; 
  395.    r = r->child[left];
  396.  
  397.   }
  398.  
  399.   // reverse chaining of leaves v...w
  400.  
  401.   if (count > 2)
  402.   { l = v->child[left];
  403.     r = w->child[right];
  404.   
  405.     r->child[left] = v;
  406.   
  407.     bin_tree_node* p = v; 
  408.   
  409.     while(p != w)
  410.     { bin_tree_node* q = p->child[right];
  411.       p->child[left] = q;
  412.       p = q;
  413.      }
  414.   
  415.     w->child[left] = l;
  416.   
  417.     p = r;
  418.   
  419.     while ( p != l )
  420.     { bin_tree_node* q = p->child[left];
  421.       q->child[right] = p;
  422.       p = q;
  423.      }
  424.    }
  425.   
  426.  
  427.   // adjust min pointer
  428.   
  429.   if (v == min_ptr()) min_ptr() = w;
  430.  
  431.  }
  432.  
  433.  
  434. //------------------------------------------------------------------
  435. // operator=
  436. //------------------------------------------------------------------
  437.  
  438. bin_tree& bin_tree::operator=(const bin_tree& t)
  439. {
  440.    if (this == &t) return *this;
  441.  
  442.    clear();
  443.  
  444.    if ( t.root() )   
  445.    { bin_tree_node* pre = 0;
  446.      root() = t.copy_tree(t.root(),pre);
  447.      root()->parent = &ROOT;
  448.      pre->corr = &ROOT;
  449.      ROOT.i = t.ROOT.i;
  450.      min_ptr() = root();
  451.      while (min_ptr()->child[left]) min_ptr() = min_ptr()->child[left];
  452.      min_ptr()->child[left] = pre;
  453.      pre->child[right] = min_ptr();
  454.      count = t.count;
  455.    }
  456.  
  457.    return *this; 
  458. }
  459.  
  460. //------------------------------------------------------------------
  461. // copy constructor
  462. //------------------------------------------------------------------
  463.  
  464.   bin_tree::bin_tree(const bin_tree& t)
  465.   { root()  = min_ptr() = 0 ;
  466.     count = t.count; 
  467.     if ( t.root() ) 
  468.     { bin_tree_node* pre = 0;
  469.       root() = t.copy_tree(t.root(),pre);
  470.       min_ptr() = root();
  471.       root()->parent = &ROOT;
  472.       while (min_ptr()->child[left]) min_ptr() = min_ptr()->child[left];
  473.       min_ptr()->child[left] = pre;
  474.       pre->child[right] = min_ptr();
  475.      }
  476.   }
  477.  
  478.  
  479. //------------------------------------------------------------------
  480. // copy_tree(p) makes a copy of tree with root p and returns a pointer to the
  481. // root of the copy. pre is last created leaf ( leaves are created from left 
  482. // to right).
  483. //------------------------------------------------------------------
  484.  
  485. bin_tree_node* bin_tree::copy_tree( bin_tree_node* p, bin_tree_item& pre) const
  486. {
  487.   bin_tree_node* q = new bin_tree_node(p);  // q = p
  488.  
  489.   if ( p->is_node() )  // internal node: copy subtrees 
  490.   {
  491.     q->child[left] = copy_tree(p->child[left],pre);
  492.     pre->corr = q;
  493.     q->child[right] = copy_tree(p->child[right],pre);
  494.     q->child[left]->parent = q;
  495.     q->child[right]->parent = q;
  496.   }
  497.   else   //leaf: chaining with last created leaf "pre"
  498.   {
  499.     copy_key(q->k);
  500.     copy_inf(q->i);
  501.  
  502.     if (pre) pre->child[right] = q; 
  503.     q->child[left] = pre;
  504.     pre = q;
  505.  
  506.    }
  507.  
  508.   return q;
  509. }
  510.  
  511. //------------------------------------------------------------------
  512. // clear
  513. //------------------------------------------------------------------
  514.  
  515. void bin_tree::clear() 
  516. {
  517.    if ( root() )
  518.    { del_tree(root());
  519.      root() = min_ptr() = 0;
  520.      count = 0;
  521.    }
  522. }
  523.  
  524. //------------------------------------------------------------------
  525. // del_tree(p) : deletes subtree rooted at node p
  526. //------------------------------------------------------------------
  527.  
  528. void bin_tree::del_tree(bin_tree_node* p)
  529. {
  530.   if ( p->is_node() )
  531.   { del_tree(p->child[left]);
  532.     del_tree(p->child[right]);
  533.    }
  534.   else
  535.   { clear_key(p->k);
  536.     clear_inf(p->i);
  537.     clear_iinf(p->corr->i);
  538.    }
  539.  
  540.   delete p;
  541. }
  542.  
  543.  
  544.  
  545.  
  546. //----------------------------------------------------------------------------
  547. // printing and drawing trees
  548. //----------------------------------------------------------------------------
  549.  
  550. void bin_tree::print() const
  551. { 
  552.   cout << endl;
  553.   cout << "size = " << size() << endl;
  554.  
  555.   if ( root() ) print_tree(root(),1);
  556.  
  557.   register bin_tree_node* q = max() ;
  558.  
  559.   if( q ) {
  560.     newline; 
  561.     print_inf( inf(q) ) ;
  562.  
  563.     while( (q=pred(q)) ) { 
  564.       print_inf( inf(q->corr) ) ;
  565.       print_inf( inf(q) ) ;
  566.     }
  567.   }
  568.   newline;
  569. }
  570.  
  571.  
  572. void bin_tree::print_tree(bin_tree_node* p,int h) const
  573. {  
  574.   if ( p->is_node() ) print_tree(p->child[right],h+1);
  575.  
  576.  for( int j=1; j <= h ; j++ ) cout << "     ";
  577.  
  578.  print_key(key(p));
  579.  cout << " (" << p->get_bal() <<")";
  580.  
  581.  if ( p->is_leaf() )
  582.  { cout << "[" << int(p) << "] ";  
  583.    cout << " succ[" << int(p->child[right]) << "] ";  
  584.    print_key(key(p->child[right]));
  585.    cout << " pred[" << int(p->child[left]) << "] "; 
  586.    print_key(key(p->child[left]));
  587.    newline;
  588.  }
  589.  else cout << "\n";
  590.  
  591.  if ( p->is_node() ) print_tree(p->child[left],h+1);
  592. }
  593.  
  594.         
  595.  
  596. void bin_tree::draw(DRAW_BIN_NODE_FCT draw_node,
  597.                     DRAW_BIN_NODE_FCT draw_leaf,
  598.                     DRAW_BIN_EDGE_FCT draw_edge, 
  599.                     double x1, double x2, double y, double ydist)
  600. { 
  601.   // draw a picture of the tree using the functions
  602.   // draw_node(x,y,k,b)   draws node with key k and balance b at (x,y)
  603.   // draw_leaf(x,y,k,b)   draws leaf with key k and balance b at (x,y)
  604.   // draw_edge(x,y,x',y') draws an edge from (x,y) to (x',y')
  605.  
  606.   draw(draw_node,draw_leaf,draw_edge,root(),x1,x2,y,ydist,0); 
  607.  }
  608.  
  609.  
  610.  
  611. void bin_tree::draw(DRAW_BIN_NODE_FCT draw_node,
  612.                     DRAW_BIN_NODE_FCT draw_leaf,
  613.                     DRAW_BIN_EDGE_FCT draw_edge, 
  614.                     bin_tree_node* r, 
  615.                     double x1, double x2, double y, 
  616.                     double ydist, double last_x)
  617. { 
  618.   // draw subtree rooted at r
  619.  
  620.   double x = (x1+x2)/2;
  621.  
  622.   if (r==nil) return;
  623.  
  624.   if (last_x != 0) draw_edge(last_x,y+ydist,x,y);
  625.  
  626.   if (r->is_node()) 
  627.      { draw_node(x,y,r->k,r->get_bal());
  628.        draw(draw_node,draw_leaf,draw_edge, r->child[0],x1,x,y-ydist,ydist,x);
  629.        draw(draw_node,draw_leaf,draw_edge, r->child[1],x,x2,y-ydist,ydist,x);
  630.       }
  631.   else
  632.      draw_leaf(x,y,r->k,r->get_bal());
  633. }
  634.  
  635.  
  636.